package com.cet.programmercarl.algorithmperformancanalysis.字符串;

/**
 * @program: algorithm
 * @description: 颠倒字符串中的单词
 * @author: 陈恩涛
 * @create: 2022-03-19 11:36
 **/
public class LC151 {

    /**
     * 暴力法，错错错
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        int leftStart = 0;
        int rightEnd = s.length() - 1;
        StringBuilder leftTemp = new StringBuilder();
        StringBuilder rightTemp = new StringBuilder();

        while (leftStart < rightEnd) {
            while (s.charAt(leftStart) == ' ') {
                leftStart++;
            }
            int leftEnd = leftStart;
            while (s.charAt(leftEnd) != ' ') {
                leftEnd++;
            }
            rightTemp = new StringBuilder(s.substring(leftStart, leftEnd)).append(rightTemp);
            leftStart = leftEnd;
            while (s.charAt(leftStart) == ' ') {
                leftStart++;
            }
            if (leftStart < rightEnd) {
                rightTemp = new StringBuilder(" ").append(rightTemp);
            }
            while (s.charAt(rightEnd) == ' ') {
                rightEnd--;
            }
            int rightStart = rightEnd;
            while (s.charAt(rightStart) != ' ') {
                rightStart--;
            }
            if (rightStart >= leftEnd) {
                // 什么时候拼接 " "
                leftTemp.append(s.substring(rightStart + 1, rightEnd + 1));
                if (rightStart > leftEnd) {
                    leftTemp.append(" ");
                }
                rightEnd = rightStart;
                while (s.charAt(rightEnd) == ' ') {
                    rightEnd--;
                }
            }
        }
        return leftTemp.append(rightTemp).toString();
    }

    /**
     * 思路：
     * 移除多余空格
     * 将整个字符串反转
     * 将每个单词反转
     *
     * @param s
     * @return
     */
    public static String reverseWords2(String s) {
        String s1 = removeExtraSpace(s);
        String s2 = reverseString(s1, 0, s1.length() - 1);
        return reverseEachWord(s2);
    }

    /**
     * 移除多余的空格
     * @param s
     * @return
     */
    public static String removeExtraSpace(String s) {
        int slowIndex = 0;
        StringBuilder result = new StringBuilder();
        s = s.trim();
        for (int fastIndex = 0; fastIndex < s.length(); fastIndex++) {
            if (s.charAt(fastIndex) == ' ') {
                result.append(s.substring(slowIndex, fastIndex + 1));
                while (s.charAt(fastIndex) == ' ') {
                    fastIndex++;
                }
                slowIndex = fastIndex;
            }
        }
        return result.append(s.substring(slowIndex)).toString();
    }

    /**
     * 反转字符串中从start到end部分的字串
     * @param s
     * @param start
     * @param end
     * @return
     */
    public static String reverseString(String s, int start, int end) {
        StringBuilder result = new StringBuilder();
        result.append(s.substring(0, start));
        StringBuilder endString = end >= s.length() - 1 ? new StringBuilder() : new StringBuilder(s.substring(end + 1));
        while (start < end) {
            result.append(s.charAt(end));
            endString = new StringBuilder(s.substring(start, start + 1)).append(endString);
            start++;
            end--;
        }
        return start == end ? result.append(s.charAt(start)).append(endString).toString() : result.append(endString).toString();
    }

    /**
     * 将字符串中的每一个单词的字母颠倒
     * @param s
     * @return
     */
    public static String reverseEachWord(String s) {
        int slowIndex = 0;
        StringBuilder result = new StringBuilder();
        for (int fastIndex = 0; fastIndex < s.length(); fastIndex++) {
            if (s.charAt(fastIndex) == ' ') {
                String word = s.substring(slowIndex, fastIndex);
                result.append(reverseString(word, 0, word.length() - 1)).append(" ");
                slowIndex = fastIndex + 1;
            }
        }
        return result.append(reverseString(s.substring(slowIndex), 0, s.substring(slowIndex).length() - 1)).toString();
    }


    public static void main(String[] args) {
//        System.out.println(removeExtraSpace("  hello  world  "));
//        System.out.println(reverseString("abc edf", 0, 3));
//        System.out.println(reverseEachWord("abc def ghi"));
        System.out.println(reverseWords2("  hello  world  "));
    }
}
